#ifndef TRIE_HPP
#define TRIE_HPP

#include <memory.h>

template <class T, size_t AlphabetSize, size_t MaxSize>
class prefix_tree
{
    int nodes[MaxSize+1][AlphabetSize];
    int num_nodes;

public:
    prefix_tree() : num_nodes(0) 
    {
        memset(nodes[0], 0, sizeof(nodes[0]));
    }

    /* Clears the tree. */
    void clear()
    {
        num_nodes = 0;
        memset(nodes[0], 0, sizeof(nodes[0]));
    }

    /* Returns the number of nodes in the tree, excluding the root. */
    size_t size() const { return num_nodes; }

    /* Adds the string 's' of length 'len' into the prefix tree. Returns true
     * if a new node was created, or false if the string is fully contained in
     * the existing tree.
     */
    bool add_string(const T* s, size_t len)
    {
        size_t i, k = 0;

        /* Walk down the trie along the prefix of s. */
        for (i = 0; i < len; i++)
        {
            if (nodes[k][s[i]] == 0) /* not exists */
                break;
            k = nodes[k][s[i]];
        }
        if (i == len) /* the string is fully contained in the trie */
            return false;

        /* Add the remaining characters into to the tree. */
        memset(nodes[num_nodes+1], 0, sizeof(nodes[0])*(len - i));
        for (; i < len; i++)
        {
            k = nodes[k][s[i]] = ++num_nodes;
        }
        return true;
    }
};

#endif /* TRIE_HPP */
